#include <iostream>
#include <vector>
#include <hash_map>
#include <stdlib.h>
#include <sys/time.h>
#include <fstream>
using namespace std;
using namespace __gnu_cxx;

int simpleRecursion(int N)
{
    if(N<1) return 0;
    if(1 == N) return 1;
    if(2 == N) return 2;
    else return simpleRecursion(N-1) + simpleRecursion(N-2);
}

int hash_map_solve(int N, hash_map<int,int> Map)
{
    if(N<1) return 0;
    if(1 == N) return 1;
    if(2 == N) return 2;

    if(Map.find(N) != Map.end()){
        return Map[N];
    }
    else{
        int value = hash_map_solve(N-1,Map) + hash_map_solve(N-2,Map);
        Map[N] = value;
        return value;
    }
}

int dynamic_plan(int N)
{
    if(N<1) return 0;
    if(1 == N) return 1;
    if(2 == N) return 2;
    int a = 1;
    int b = 2;
    int temp;
    for (int i = 3; i <= N; ++i) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return temp;
}

int climbStep(int argc, char *argv[])
{
    if(argc != 3) return -1;
    if(1 == atoi(argv[2]))
    {
        timeval begin,end;
        gettimeofday(&begin,NULL);
        int result = simpleRecursion(atoi(argv[1]));
        gettimeofday(&end,NULL);
        double timeCount = (end.tv_sec - begin.tv_sec)*1000.f
                + (end.tv_usec - begin.tv_usec)/1000.f;
        cout << "simpleRecursion return:  " << result << " with time[" << timeCount <<" ms]" << std::endl;
    }
    else if(2 == atoi(argv[2]))
    {
        timeval begin,end;
        gettimeofday(&begin,NULL);
        hash_map<int,int> map_;
        int result = hash_map_solve(atoi(argv[1]),map_);
        gettimeofday(&end,NULL);
        double timeCount = (end.tv_sec - begin.tv_sec)*1000.f
                + (end.tv_usec - begin.tv_usec)/1000.f;
        cout << "hash_map return:         " << result << " with time[" << timeCount <<" ms]" << std::endl;
    }
    else if(3 == atoi(argv[2]))
    {
        timeval begin,end;
        gettimeofday(&begin,NULL);
        int result = dynamic_plan(atoi(argv[1]));
        gettimeofday(&end,NULL);
        double timeCount = (end.tv_sec - begin.tv_sec)*1000.f
                + (end.tv_usec - begin.tv_usec)/1000.f;
        cout << "dynamic_plan return:     " << result << " with time[" << timeCount <<" ms]" << std::endl;
    }

    return 0;
}

int solveMineDynamic(int Workers,int Mines, vector<int> mineWorkers,vector<int> mineGold)
{
    std::vector<int> preResults(Workers,0);
    std::vector<int> results(Workers,0);

    //!< fill zero
    for (int i = 0; i < Workers; ++i) {
        if( i+1 < mineWorkers[0] )
            preResults[i] = 0;
        else
            preResults[i] = mineGold[0];
    }

    //!< filed other
    for (int mineIdx = 1; mineIdx < Mines; ++mineIdx) {
        for (int workerIdx = 0; workerIdx < Workers; ++workerIdx) {
            if(workerIdx+1 < mineWorkers[mineIdx]){
                results[workerIdx] = preResults[workerIdx];
            }
            else{
                results[workerIdx] = std::max(preResults[workerIdx],preResults[workerIdx-mineWorkers[mineIdx]] + mineGold[mineIdx]);
            }
        }
        std::swap(preResults,results);
    }
    return results[Workers-1];
}

int solveMineRecursion(int Workers,int Mines, vector<int> mineWorkers,vector<int> mineGold)
{
    if(Mines<=0) return 0;
    if(Mines == 1 && Workers < mineWorkers[0]){
        return 0;
    }
    else if(1 == Mines && Workers > mineWorkers[0]){
        return mineGold[0];
    }
    else if(Mines > 1 && Workers < mineWorkers[Mines-1]){
        return solveMineRecursion(Workers,Mines-1,mineWorkers,mineGold);
    }
    else{
        return std::max(solveMineRecursion(Workers,Mines-1,mineWorkers,mineGold),
                        solveMineRecursion(Workers-mineWorkers[Mines-1],Mines-1,mineWorkers,mineGold)+mineGold[Mines-1]);
    }
}

int mineProblem()
{
    int Workers;
    int Mines;
    ifstream ifs("data.txt");
    if(!ifs.is_open())
    {
        cout << "data file open failed!\n";
        exit(-1);
    }
    ifs >> Workers;
    ifs >> Mines;

    vector<int> mineWorkers(Mines,0);
    vector<int> mineGold(Mines,0);
    for (int index = 0; index < Mines; ++index) {
        ifs >> mineWorkers[index];
        ifs >> mineGold[index];
    }

    for (int index = 0; index < Mines; ++index) {
        cout << "No[" << index << "]: needWorkers: ";
        cout << mineWorkers[index];
        cout << ", have gold: ";
        cout <<  mineGold[index] << "\n";
    }

    ////////////////////////////////////////////////////////////
    timeval begin,end;
    gettimeofday(&begin,NULL);
    int result = solveMineRecursion(Workers,Mines,mineWorkers,mineGold);
    gettimeofday(&end,NULL);
    double timeCount = (end.tv_sec - begin.tv_sec)*1000.f
            + (end.tv_usec - begin.tv_usec)/1000.f;

    cout << "the max gold of Recursion is : " << result << " with time: " << timeCount << endl;

    ////////////////////////////////////////////////////////////////////////////////
    gettimeofday(&begin,NULL);
    result = solveMineDynamic(Workers,Mines,mineWorkers,mineGold);
    gettimeofday(&end,NULL);
    timeCount = (end.tv_sec - begin.tv_sec)*1000.f
            + (end.tv_usec - begin.tv_usec)/1000.f;

    cout << "the max gold of Dynamic is   : " << result << " with time: " << timeCount << endl;
}

class FindLongestIncreasePath
{
public:
    FindLongestIncreasePath():
         directY{0,  0,  1, -1},directX{1, -1,  0,  0}
    {}
    int FindLongestIncreasePathMethod(const std::vector<std::vector<int> >& matrix)
    {
        if(matrix.empty() || matrix[0].empty()){
            cout << "matrix is empty!\n"  << "matrix.size() = " << matrix.size() << endl;
            return 0;
        }
        rows = matrix.size();
        cols = matrix[0].size();

        cout << "rows[" << rows << "] cols[" << cols << "]\n";
        dp   = new int[rows*cols];
        flag = new int[rows*cols];

        int result = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                searchPath(i,j,matrix);
                result = std::max(result,dp[i*cols+j]);
            }
        }
        return result;
    }

    int searchPath(int i,int j,const std::vector<std::vector<int> >& matrix)
    {
        if(0 != flag[i*cols+j])
            return dp[i*cols+j];
        int result = 1;
        int nx, ny;
        for (int index = 0; index < 4; ++index) {
            nx = i + directX[index];
            ny = j + directY[index];
            if(nx>=0 && ny>=0 && nx<rows && ny<cols)
            {
                if(matrix[i][j] < matrix[nx][ny])
                {
                    result = std::max(result,searchPath(nx,ny,matrix)+1);
                }
            }
        }
        flag[i*cols+j] = 1;
        dp[i*cols+j] = result;
        return result;
    }

protected:
    int rows,cols;
    int maxLen, curLen;
    int *dp;
    int *flag;
    const int directX[4];
    const int directY[4];
};

int longestIncreasePath()
{
    ifstream ifs("matrixData.txt");
    if(!ifs.is_open())
    {
        cout << "data file open failed!\n";
        exit(-1);
    }
    int cols,rows;
    ifs >> rows;
    ifs >> cols;
    std::vector<std::vector<int> > matrix(rows);
    matrix.resize(rows);
    for (int i = 0; i < rows; ++i) {
        matrix[i].resize(cols);
        for (int j = 0; j < cols; ++j) {
            ifs >> matrix[i][j];
        }
    }

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    FindLongestIncreasePath path;
    cout << "LongestIncreasePath = " << path.FindLongestIncreasePathMethod(matrix) << endl;
}

int main(int argc, char *argv[])
{
    if(argc==1) cout << "Usage: ./dynamic N_step method_id\n"
                        "\t\t     -- method_id : 1 simpleRecursion;\n"
                        "\t\t                    2 hash_map;\n"
                        "\t\t                    3 dynamic_plan;\n";

    else if(1 == atoi(argv[1])) climbStep(argc-1,argv+1);
    else if(2 == atoi(argv[1])) mineProblem();
    else longestIncreasePath();
    return 0;
}

